package gamehistory.utils.computation;

import java.text.MessageFormat;
import java.util.ArrayList;

/**
 * A class representing a polynomial.
 * Used to perform calculations on probabilistic polynomials.
 * Currently, all terms of the polynomial are distributed into the form ...ax^3 + bx^2 + xc^1 + d... etc
 * Based on http://www.cs.princeton.edu/introcs/92symbolic/Polynomial.java.html
 * @author Team Nerdicide - Brent Kersanske and Brad Lajoie
 * @since 9/30/2009
 * @version Last modified 10/1/2009
 */
public class Polynomial {
	
	/* Log messages */
	private static final String MSG_ERROR_INDEX_OUT_OF_RANGE       = "The index {0} is out of range for the array list of coefficients with size {1}";

	private ArrayList<Double> coefficients;
	
	private int degree;

	/**
	 * Index of the coefficient corresponds to the exponent of that term
	 * 
	 * e.g. coefficient at index 2, means a p^3. We only have one variable, p.
	 * 
	 * @param coefficient The coefficient of the term.
	 * @param exponentOfTheTerm Power to which the polynomial term is raised.
	 */
    public Polynomial(double coefficient, int exponentOfTheTerm) {
    	coefficients = generateDefaultCoefficientList(exponentOfTheTerm+1);
        setCoefficientAtIndex(exponentOfTheTerm, coefficient);
        updateDegree();
    }
    
    /**
     * Prepopulates coefficients with 0's.
     * @param size
     * @return
     */
    private ArrayList<Double> generateDefaultCoefficientList(int size) {
    	ArrayList<Double> newCoefficientList = new ArrayList<Double> ();
    	for(int i = 0; i < size; i++) {
    		newCoefficientList.add(Double.valueOf(0));
    	}
    	return newCoefficientList;
    }

    /**
     * Gets the degree of this polynomial.
     * @return The degree of the polynomial.
     */
    public int getDegree() {
    	return this.degree;
    }
    
    /**
     * Updates the degree of the polynomial. Used when changes to the coefficients occur. 
     */
    public void updateDegree() {
    	int theDegree = 0;
    	for(int i = 0; i < coefficients.size(); i++) {
    		if(getCoefficientAtIndex(i) != 0) {
    			theDegree = i;
    		}
    	}
    	this.degree = theDegree;
    }
    
    /**
     * Replaces the coefficient at the given index with the given coefficient.
     * @param index The index of the coefficient to replace.
     * @param coefficient The coefficient that will do the replacing.
     */
    public void setCoefficientAtIndex(int index, double coefficient) {
    	if(index >= this.coefficients.size()) {
    		throw new RuntimeException(MessageFormat.format(MSG_ERROR_INDEX_OUT_OF_RANGE, index, this.coefficients.size()));
    	}
    	this.coefficients.set(index, Double.valueOf(coefficient));
    }
    
    /**
     * Gets the coefficient at the given index.
     * @param index The index of the given index to retrieve.
     * @return The Coefficient at the given index.
     * @throws RuntimeException Thrown if the provided index is out of range for the list of coefficients.
     */
    public Double getCoefficientAtIndex(int index) throws RuntimeException {
    	if(index >= this.coefficients.size()) {
    		throw new RuntimeException(MessageFormat.format(MSG_ERROR_INDEX_OUT_OF_RANGE, index, this.coefficients.size()));
    	}
    	return this.coefficients.get(index);
    	
    }
    
    /**
     * Is this polynomial linear?
     * @return boolean true if the polynomial is linear, false if it is not.
     */
    public boolean isLinear() {
    	return this.getDegree() == 1;
    }
    
    /**
     * Is this polynomial quadratic?
     * @return boolean true if the polynomial is quadratic, false if it is not.
     */
    public boolean isQuadratic() {
    	return this.getDegree() == 2;
    }

    /**
     * Gets the resulting polynomial when this polynomial is added with another.
     * @param other The other polynomial to add to this one.
     * @return The sum polynomial
     */
    public Polynomial add(Polynomial other) {
    	Polynomial sum = new Polynomial(0, Math.max(this.getDegree(), other.getDegree()));
    	
    	for(int i = 0; i <= this.getDegree(); i++) {
    		sum.setCoefficientAtIndex(i, (sum.getCoefficientAtIndex(i) + this.getCoefficientAtIndex(i)));
    	}
    	
    	for(int j = 0; j <= other.getDegree(); j++) {
    		sum.setCoefficientAtIndex(j, (sum.getCoefficientAtIndex(j) + other.getCoefficientAtIndex(j)));
    	}
    	
    	sum.updateDegree();
    	
    	return sum;
    }

    /**
     * Gets the resulting polynomial when a given polynomial is subtracted from this one.
     * @param other The polynomial to subtract from this polynomial.
     * @return The resulting difference polynomial.
     */
    public Polynomial subtract(Polynomial other) {
    	
    	Polynomial difference = new Polynomial(0, Math.max(this.getDegree(), other.getDegree()));
    	
    	for(int i = 0; i <= this.getDegree(); i++) {
    		difference.setCoefficientAtIndex(i, (difference.getCoefficientAtIndex(i) + this.getCoefficientAtIndex(i)));
    	}
    	
    	for(int j = 0; j <= other.getDegree(); j++) {
    		difference.setCoefficientAtIndex(j, (difference.getCoefficientAtIndex(j) - other.getCoefficientAtIndex(j)));
    	}
    	
    	difference.updateDegree();
    	return difference;
    	
    }
    
    /**
     * Gets the resulting polynomial when this polynomial is multiplied by a given polynomial.
     * @param other The polynomial to multiply this polynomial by.
     * @return The resulting product polynomial.
     */
    public Polynomial multiply(Polynomial other) {
    	
    	Polynomial product = new Polynomial(0, this.getDegree() + other.getDegree());
    	
    	for(int i = 0; i <= this.getDegree(); i++) {
    		for(int j = 0; j <= other.getDegree(); j++) {
    			product.setCoefficientAtIndex(i + j, (product.getCoefficientAtIndex(i + j) + (this.getCoefficientAtIndex(i) * other.getCoefficientAtIndex(j))));
    		}
    	}
    	product.updateDegree();
    	return product;
    }
    
    /**
     * Gets the resulting polynomial when this polynomial is composed of a given polynomial.
     * @param other The polynomial to compose this polynomial with.
     * @return The resulting composition polynomial.
     */
    public Polynomial compose(Polynomial other) {
    	Polynomial composition = new Polynomial(0, 0);    	
    	for(int i = this.getDegree(); i >= 0; i--) {
    		Polynomial term = new Polynomial(this.getCoefficientAtIndex(i), 0);
    		composition     = term.add(other.multiply(composition));
    	}    	
    	return composition;
    }

    /**
     * Evaluates this polynomial for the given value of P.
     * @param p The value to evaluate the polynomial for.
     * @return The evaluation for the given p.
     */
    public double evaluate(double p) {
    	double currentResult = 0;     	
    	for(int i = this.getDegree(); i >= 0; i--) {
    		currentResult = this.getCoefficientAtIndex(i) + (p * currentResult);
    	}    	
    	return currentResult;
    }
    
    /**
     * Retrieves the maximum p assignment for this polynomial within the range of 0 and 1.
     * Maximum p values are retrieved differently depending on the type of polynomial.
     * Currently, only linear and quadratic polynomials are supported.
     * @return The maximum p assignment for this polynomial.
     */
    public double retrieveMaximumPValue() {
    	if(isLinear()) {
    		return retrieveMaximumPValueForLinearPolynomial();
    	} else if(isQuadratic()) {
    		return retrieveMaximumPValueForQuadraticPolynomial();
    	}     	
    	return 0;
    }
    
	/**
	 * Retrieves the maximum p value when we set this linear polynomial equal to 0 
	 * @return double The maximum p value computed.
	 */
	private double retrieveMaximumPValueForLinearPolynomial() {
		
		double pValue = 0;
		double a      = this.getCoefficientAtIndex(this.getDegree());
		double b      = this.getCoefficientAtIndex(this.getDegree() - 1);		
		// First bring the constant over to the "0 side"
		pValue -= b;
		// Divide the pValue by the coefficient of the p in the polynomial if its not 0
		if(a != 0) {
			pValue /= a;
		}				
		return pValue;
	}
	
	/**
	 * Retrieves the maximum p value when we set this quadratic polynomial equal to 0.
	 * Uses the quadratic formula to compute two values, and then returns the value between
	 * the range of 0 and 1.
	 * @return The maximum p value for this quadratic polynomial.
	 */
	private double retrieveMaximumPValueForQuadraticPolynomial() {

		double a        = this.getCoefficientAtIndex(this.getDegree());
		double b        = this.getCoefficientAtIndex(this.getDegree() - 1);
		double c        = this.getCoefficientAtIndex(this.getDegree() - 2);
		double pValueA  = ((-b - Math.sqrt(Math.pow(b, 2) - 4 * a * c))/(2 * a));
		double pValueB  = ((-b + Math.sqrt(Math.pow(b, 2) - 4 * a * c))/(2 * a));		

		if((pValueA > 0 && pValueA < 1) &&
		   (pValueB > 0 && pValueB < 1)) {
			double pValue = Math.max(pValueA, pValueB);
			return(pValue);
		}
		
		if(pValueA > 0 && pValueA < 1) {
			return pValueA;
		} else if(pValueB > 0 && pValueB < 1) {
			return pValueB;
		}	
		return 0;
	}

    /**
     * Gets the derivative polynomial of this polynomial.
     * @return The derivative of this polynomial.
     */
    public Polynomial differentiate() {
    	if(this.getDegree() == 0) {
    		return new Polynomial(0, 0);
    	}    	
    	Polynomial derivative = new Polynomial(0, this.getDegree() - 1);
    	derivative.degree = degree - 1;
    	for(int i = 0; i < this.getDegree(); i++) {
    		derivative.setCoefficientAtIndex(i, ((i + 1) *  this.getCoefficientAtIndex(i + 1)));
    	}
    	return derivative;
    }
    
    /**
     * Gets the maximum bias value for this polynomial.
     * Evaluates with the p value of the derivative of this polynomial.
     * @return The maximum bias value for this polynomial.
     */
    public double getBreakEven() {
    	if(this.degree != 0) {
    		double maxBias       = this.getMaxBias();
    		double valueWithMaxP = this.evaluate(maxBias);
    		double valueAtZero   = this.evaluate(0);
    		double valueAtOne    = this.evaluate(1);
    		return getBestValue(valueWithMaxP, valueAtZero, valueAtOne); 
    	} 
    	return 0.0;
    }
    
    private double getMaxBias() {
    	return this.differentiate().retrieveMaximumPValue();    	
    }
    
    /**
     * 
     * @param a
     * @param b
     * @param c
     * @return
     */
    private double getBestValue(double a, double b, double c) {
    	if(isBestValue(a, b, c)) {
    		return a;
    	} else if(isBestValue(b, a, c)) {
    		return b;
    	} else if(isBestValue(c, a, b)) {
    		return c;
    	} else{
    		return 1;
    	}
    }
    
    /**
     * 
     * @param bestValueCandidate
     * @param otherA
     * @param otherB
     * @return
     */
    private boolean isBestValue(double bestValueCandidate, double otherA, double otherB) {
    	return((isEvaluationWithinRange(bestValueCandidate)) && 
    		   (bestValueCandidate >= otherA)                && 
    		   (bestValueCandidate >= otherB));
    }
    
    /**
     * 
     * @param value
     * @return
     */
    private boolean isEvaluationWithinRange(double value) {
    	return((value > 0) && (value <= 1));
    }
}
